{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flower Planting With No Adjacent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: gardenNoAdj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不邻接植花"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个花园，按从&nbsp;<code>1</code>&nbsp;到 <code>n</code> 标记。另有数组 <code>paths</code> ，其中 <code>paths[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;描述了花园&nbsp;<code>x<sub>i</sub></code> 到花园&nbsp;<code>y<sub>i</sub></code> 的双向路径。在每个花园中，你打算种下四种花之一。</p>\n",
    "\n",
    "<p>另外，所有花园 <strong>最多</strong> 有 <strong>3</strong> 条路径可以进入或离开.</p>\n",
    "\n",
    "<p>你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。</p>\n",
    "\n",
    "<p><em>以数组形式返回 <strong>任一</strong> 可行的方案作为答案&nbsp;<code>answer</code>，其中&nbsp;<code>answer[i]</code>&nbsp;为在第&nbsp;<code>(i+1)</code>&nbsp;个花园中种植的花的种类。花的种类用 &nbsp;1、2、3、4 表示。保证存在答案。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, paths = [[1,2],[2,3],[3,1]]\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "<strong>解释：</strong>\n",
    "花园 1 和 2 花的种类不同。\n",
    "花园 2 和 3 花的种类不同。\n",
    "花园 3 和 1 花的种类不同。\n",
    "因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, paths = [[1,2],[3,4]]\n",
    "<strong>输出：</strong>[1,2,1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]\n",
    "<strong>输出：</strong>[1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= paths.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>paths[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>x<sub>i</sub> != y<sub>i</sub></code></li>\n",
    "\t<li>每个花园 <strong>最多</strong> 有 <strong>3</strong> 条路径可以进入或离开</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flower-planting-with-no-adjacent](https://leetcode.cn/problems/flower-planting-with-no-adjacent/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flower-planting-with-no-adjacent](https://leetcode.cn/problems/flower-planting-with-no-adjacent/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,2],[2,3],[3,1]]', '4\\n[[1,2],[3,4]]', '4\\n[[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        ch=[[] for _ in range(1+n)]\n",
    "        for u,v in paths:\n",
    "            ch[u].append(v)\n",
    "            ch[v].append(u)\n",
    "        res=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            can=[1,2,3,4]\n",
    "            for c in ch[i]:\n",
    "                if res[c] in can:\n",
    "                    can.remove(res[c])\n",
    "            res[i]=can[0]\n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in paths:\n",
    "            graph[x - 1].append(y - 1)\n",
    "            graph[y - 1].append(x - 1)\n",
    "        \n",
    "        color = [0] * n\n",
    "\n",
    "        for i, nodes in enumerate(graph):\n",
    "            color[i] = (set(range(1, 5)) - {color[j] for j in nodes}).pop()\n",
    "        return color\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        neighbor=dict()\n",
    "        for path in paths:\n",
    "            if max(path) not in neighbor:\n",
    "                neighbor[max(path)]=[]\n",
    "            neighbor[max(path)].append(min(path))\n",
    "        res=[]\n",
    "        for i in range(1,n+1):\n",
    "            ban=[]\n",
    "            if i in neighbor:\n",
    "                for node in neighbor[i]:\n",
    "                    ban.append(res[node-1])\n",
    "            for color in [1,2,3,4]:\n",
    "                if color not in ban:\n",
    "                    res.append(color)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        path_list = [[] for i in range(n)]\n",
    "        for i in paths:\n",
    "            path_list[i[0]-1].append(i[1]-1)\n",
    "            path_list[i[1]-1].append(i[0]-1)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            color = [1,2,3,4]\n",
    "            for j in path_list[i]:\n",
    "                if ans[j] in color:\n",
    "                    color.remove(ans[j])\n",
    "            ans[i] = color[0]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, input: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for path in input:\n",
    "            graph[path[0]-1].append(path[1]-1)\n",
    "            graph[path[1]-1].append(path[0]-1)\n",
    "        \n",
    "        ans = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            to_put = [1, 2, 3, 4]\n",
    "            for j in graph[i]:\n",
    "                if ans[j] in to_put:\n",
    "                    to_put.remove(ans[j])\n",
    "            \n",
    "            ans[i] = to_put[0]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in paths:\n",
    "            g[u - 1].append(v - 1)\n",
    "            g[v - 1].append(u - 1)  # 建图\n",
    "        color = [0] * n\n",
    "        for i, nodes in enumerate(g):\n",
    "            color[i] = (set(range(1, 5)) - {color[j] for j in nodes}).pop()\n",
    "        return color\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/flower-planting-with-no-adjacent/solutions/2227318/liang-chong-xie-fa-ha-xi-biao-shu-zu-wei-7hm8/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for i in range(n)]\n",
    "        for path in paths:\n",
    "            adj[path[0] - 1].append(path[1] - 1)\n",
    "            adj[path[1] - 1].append(path[0] - 1)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            colored = [False] * 5\n",
    "            for vertex in adj[i]:\n",
    "                colored[ans[vertex]] = True\n",
    "            for j in range(1, 5):\n",
    "                if not colored[j]:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        # 题意，就是给你花园直接连接的路径，然后你需要给每个花园选择花的种类保证相连路径的花的种类不同\n",
    "        # 想法，枚举每一个花园的选择，然后看前面选的花园是否对现在的花园有影响\n",
    "        \n",
    "        # 建图\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in paths:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        # 枚举\n",
    "        color = [0]*n\n",
    "        for i,nodes in enumerate(g):\n",
    "            color[i] = (set(range(1,5))-{color[j] for j in nodes}).pop()\n",
    "        return color"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for i in range(n)]\n",
    "        for path in paths:\n",
    "            adj[path[0] - 1].append(path[1] - 1)\n",
    "            adj[path[1] - 1].append(path[0] - 1)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            colored = [False] * 5\n",
    "            for vertex in adj[i]:\n",
    "                colored[ans[vertex]] = True\n",
    "            for j in range(1, 5):\n",
    "                if not colored[j]:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in paths:\n",
    "            graph[x - 1].append(y - 1)\n",
    "            graph[y - 1].append(x - 1)\n",
    "        \n",
    "        ans = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            used = {ans[j] for j in graph[i]}\n",
    "            for flower in range(1, 5):\n",
    "                if flower not in used:\n",
    "                    ans[i] = flower\n",
    "                    break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in paths:\n",
    "            g[u - 1].append(v - 1)\n",
    "            g[v - 1].append(u - 1)  # 建图\n",
    "        color = [0] * n\n",
    "        for i, nodes in enumerate(g):\n",
    "            color[i] = (set(range(1, 5)) - {color[j] for j in nodes}).pop()\n",
    "        return color"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        grid = [[] for _ in range(n)]\n",
    "        for u, v in paths:\n",
    "            grid[u-1].append(v-1)\n",
    "            grid[v-1].append(u-1)\n",
    "        ans = [0]*n\n",
    "        for i, g in enumerate(grid):\n",
    "            mask = 1\n",
    "            for j in grid[i]:\n",
    "                mask |= 1<<ans[j]\n",
    "            mask = ~mask\n",
    "            ans[i] = (mask&(-mask)).bit_length() - 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for i in range(n)]\n",
    "        for path in paths:\n",
    "            adj[path[0] - 1].append(path[1] - 1)\n",
    "            adj[path[1] - 1].append(path[0] - 1)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            colored = [False] * 5  \n",
    "            for vertex in adj[i]:   # vertex 邻居\n",
    "                colored[ans[vertex]] = True   # 判断有哪些颜色已被标记过  colored[0] 无所谓因为没有0颜色\n",
    "            for j in range(1, 5): # 1 - 4 颜色\n",
    "                if not colored[j]:\n",
    "                    ans[i] = j # 选一个最近没标记的颜色进行标记\n",
    "                    break\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in paths:\n",
    "            g[u - 1].append(v - 1)\n",
    "            g[v - 1].append(u - 1)\n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            colored=[False]*5\n",
    "            for j in g[i]:\n",
    "                colored[ans[j]]=True\n",
    "            for j in range(1,5):\n",
    "                if not colored[j]:\n",
    "                    ans[i]=j\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\r\n",
    "        if len(paths) == 0: return [1] * n\r\n",
    "        path = {}\r\n",
    "        for x , y in paths:\r\n",
    "            if x not in path: path[x] = []\r\n",
    "            if y not in path: path[y] = []\r\n",
    "            path[x].append(y)\r\n",
    "            path[y].append(x)\r\n",
    "        results = [0] * n\r\n",
    "        results[0] = 1\r\n",
    "        for i in range(1,n):\r\n",
    "            if i+1 not in path:\r\n",
    "                results[i] = 1\r\n",
    "            else:\r\n",
    "                choice = [i for i in range(1,5)]\r\n",
    "                for j in path[i+1]:\r\n",
    "                    if j < i + 1 and results[j-1] in choice:\r\n",
    "                        choice.remove(results[j-1])\r\n",
    "                results[i] = choice[0]\r\n",
    "        \r\n",
    "        return results\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in paths:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        color = [0]*n \n",
    "        for i , nodes in enumerate(g):\n",
    "            #color[i] = (set(range(1,5)) - {color[j] for j in nodes}).pop()\n",
    "            mask = 1\n",
    "            for j in nodes:\n",
    "                mask |= 1 << color[j]\n",
    "            mask = ~mask\n",
    "            color[i] = (mask & -mask).bit_length() - 1\n",
    "        return color\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        def dfs(cur):\n",
    "            exists = []\n",
    "            for c in hs[cur]:\n",
    "                exists.append(ret[c-1])\n",
    "\n",
    "            for f in [1, 2, 3, 4]:\n",
    "                if not f in exists:\n",
    "                    ret[cur-1] = f\n",
    "                    break\n",
    "\n",
    "        ret = [0]*n\n",
    "        hs = defaultdict(lambda: [])\n",
    "        for a, b in paths:\n",
    "            hs[a].append(b)\n",
    "            hs[b].append(a)\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for u,v in paths:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        \n",
    "        color=[0]*n\n",
    "        for i,nodes in enumerate(g):\n",
    "            color[i]=(set(range(1,5))-{color[j] for j in nodes}).pop()\n",
    "        return color\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        a = [[] for i in range(n)]\n",
    "        for path in paths:\n",
    "            a[path[0] - 1].append(path[1] - 1)\n",
    "            a[path[1] - 1].append(path[0] - 1)#用a来记录邻接\n",
    "        ans = [0] * n#记录答案\n",
    "        for i in range(n):\n",
    "            colored = [False] * 5\n",
    "            for k in a[i]:\n",
    "                colored[ans[k]] = True\n",
    "            for j in range(1, 5):\n",
    "                if not colored[j]:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        res = [0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            used = {res[y-1] for y in g[i]}\n",
    "            for c in range(1, 5):\n",
    "                if c not in used:\n",
    "                    res[i-1] = c\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        grpah = [[] for _ in range(n)]\n",
    "\n",
    "        for path in paths:\n",
    "            grpah[path[0]-1].append(path[1] - 1)\n",
    "            grpah[path[1]-1].append(path[0] - 1)\n",
    "        \n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            colored = [False] * 5\n",
    "            for nx in grpah[i]:\n",
    "                colored[ans[nx]] = True\n",
    "            for j in range(1,5):\n",
    "                if not colored[j]:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        relation = defaultdict(list)\n",
    "        for g1, g2 in paths:\n",
    "            relation[g1].append(g2)\n",
    "            relation[g2].append(g1)\n",
    "        \n",
    "        result = [0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            colors = set(range(1, 5)) - set(result[j-1] for j in relation[i])\n",
    "            result[i-1] = colors.pop()\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for path in paths:\n",
    "            graph[path[0]-1].append(path[1]-1)\n",
    "            graph[path[1]-1].append(path[0]-1)\n",
    "        ans = [0]*n\n",
    "\n",
    "        def dfs(i):\n",
    "            taken = set()\n",
    "            for j in graph[i]:\n",
    "                taken.add(ans[j])\n",
    "            for x in range(1, 5):\n",
    "                if x not in taken:\n",
    "                    ans[i]=x\n",
    "                    break\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for i in range(n)]\n",
    "        for path in paths:\n",
    "            adj[path[0] - 1].append(path[1] - 1)\n",
    "            adj[path[1] - 1].append(path[0] - 1)\n",
    "        ans = [0] * n \n",
    "        for i in range(n):\n",
    "            colored = [False] * 5\n",
    "            for vertex in adj[i]:\n",
    "                colored[ans[vertex]] = True\n",
    "            for j in range(1, 5):\n",
    "                if not colored[j]:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj=[[] for i in range(n)]\n",
    "        for path in paths:\n",
    "            adj[path[0]-1].append(path[1]-1)\n",
    "            adj[path[1]-1].append(path[0]-1)\n",
    "        \n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            colored =[False]*5\n",
    "            for vertex in adj[i]:\n",
    "                colored[ans[vertex]]=True\n",
    "            for j in range(1,5):\n",
    "                if not colored[j]:\n",
    "                    ans[i]=j\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        edgeDict = [[] for row in range(n)]\n",
    "        for idx, path in enumerate(paths):\n",
    "            a = path[0] - 1\n",
    "            b = path[1] - 1\n",
    "            edgeDict[a].append(b)\n",
    "            edgeDict[b].append(a)\n",
    "\n",
    "        res = [0] * n\n",
    "        for garden in range(n):\n",
    "            colors = {1, 2, 3, 4}\n",
    "            for edge in edgeDict[garden]:\n",
    "                colors.discard(res[edge])\n",
    "            res[garden] = next(iter(colors))\n",
    "\n",
    "        return res\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    n = 3\n",
    "    paths = [[1, 2], [2, 3], [3, 1]]\n",
    "    s = Solution()\n",
    "    s.gardenNoAdj(n, paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        e=[[] for _ in range(n)]\n",
    "        for x in paths:\n",
    "            e[x[0]-1].append(x[1]-1)\n",
    "            e[x[1]-1].append(x[0]-1)\n",
    "        f=[1,2,3,4]\n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            q=Counter(f)\n",
    "            for x in e[i]:\n",
    "               if ans[x]!=0: \n",
    "                 q-=Counter([ans[x]])\n",
    "            # print(q)      \n",
    "            c=0\n",
    "            for x in q.items():\n",
    "                if x[1]==1:\n",
    "                   c=x[0]\n",
    "                break\n",
    "            ans[i]=c\n",
    "        return ans             \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "            # Create an adjacency list for the gardens\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for x, y in paths:\n",
    "            adj[x-1].append(y-1)\n",
    "            adj[y-1].append(x-1)\n",
    "\n",
    "        # Initialize the result array with zeros\n",
    "        res = [0] * n\n",
    "\n",
    "        # Plant flowers for each garden\n",
    "        for i in range(n):\n",
    "            # Find the flowers in the adjacent gardens\n",
    "            used = {res[j] for j in adj[i]}\n",
    "            # Plant a flower that's not used in the adjacent gardens\n",
    "            for f in range(1, 5):\n",
    "                if f not in used:\n",
    "                    res[i] = f\n",
    "                    break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj=[[] for i in range(n)] #建立整个图的邻接列表,什么意思？\n",
    "        for path in paths:\n",
    "            adj[path[0]-1].append(path[1]-1)\n",
    "            adj[path[1]-1].append(path[0]-1)#这是什么意思？    \n",
    "        ans=[0]*n  #将每个花园节点的颜色全部标记为0\n",
    "        for i in range(n):\n",
    "            colored=[False]*5\n",
    "            for vertex in adj[i]:\n",
    "                colored[ans[vertex]]=True\n",
    "            for j in range(1,5):#枚举四种颜色\n",
    "                if not colored[j]:\n",
    "                    ans[i]=j\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        ans=[0]*n\n",
    "        e=[[]for _ in range(n)]\n",
    "        for x in paths:\n",
    "            e[x[0]-1].append(x[1]-1)\n",
    "            e[x[1]-1].append(x[0]-1)\n",
    "        f=[1,2,3,4]\n",
    "        for i in range(n):\n",
    "          q=Counter(f)\n",
    "          for x in e[i]:\n",
    "            if ans[x]>0:\n",
    "               q-=Counter([ans[x]]) \n",
    "          for x in q.items():\n",
    "            if x[1]:  \n",
    "              ans[i]=x[0]\n",
    "              break \n",
    "        return ans      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:\n",
    "        # 思路: 对于当前的某一个花园，剔除掉与它邻接花园的花的种类，从剩下的种类中选一种即可。\n",
    "        # 1. 构建邻接矩阵G; 2. 用res列表保存当前花园花的种类\n",
    "        res = [0]*N\n",
    "        G = [[] for _ in range(N)]\n",
    "        for x, y in paths:\n",
    "            G[x - 1].append(y - 1)\n",
    "            G[y - 1].append(x - 1)\n",
    "        for i in range(N):\n",
    "            # 对于当前花园, 排除掉邻接的花园的花种就ok了，然后pop出一种\n",
    "            res[i] = ({1,2,3,4} - {res[j] for j in G[i]}).pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for i  in range(n)]\n",
    "        for path in paths:\n",
    "            adj[path[0] - 1].append(path[1] - 1)\n",
    "            adj[path[1] - 1].append(path[0] - 1)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            colored = [False]*5\n",
    "            for neighbor in adj[i]:\n",
    "                colored[ans[neighbor]] = True\n",
    "            for j in range(1, 5):\n",
    "                if colored[j] is False:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for i in range(n)]\n",
    "        for path in paths:\n",
    "            adj[path[0]-1].append(path[1]-1)\n",
    "            adj[path[1]-1].append(path[0]-1)\n",
    "        ans = [0]*n \n",
    "        for i in range(n):\n",
    "            colored = [False]*5\n",
    "            for vertex in adj[i]:\n",
    "                colored[ans[vertex]] = True\n",
    "            for j in range(1, 5):\n",
    "                if not colored[j]:\n",
    "                    ans[i] = j\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        p = [[] for _ in range(n)]\n",
    "        for x, y in paths:\n",
    "            p[x - 1].append(y - 1)\n",
    "            p[y - 1].append(x - 1)\n",
    "        \n",
    "        res = [1]\n",
    "        fs = [1, 2, 3, 4]\n",
    "        for i in range(1, n):\n",
    "            used = set()\n",
    "            for g in p[i]:\n",
    "                if g < i:\n",
    "                    used.add(res[g])\n",
    "            for f in fs:\n",
    "                if f not in used:\n",
    "                    res.append(f)\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "\n",
    "        graph = [[] for _ in range(n+1)]\n",
    "        for path in paths:\n",
    "            a, b = path[0], path[1]\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        # 从点i出发bfs at most 3 edges （如果其中有parent已经被标记颜色）\n",
    "\n",
    "        color = [0]*(n+1)\n",
    "        visited = [False]*(n+1)\n",
    "\n",
    "        def bfs(i):\n",
    "            #\n",
    "            q = collections.deque([i])\n",
    "            visited[i] = True\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                c = 0\n",
    "                for nei in graph[x]:\n",
    "                    c |= 1 << color[nei]\n",
    "                    if not visited[nei]:\n",
    "                        q.append(nei)\n",
    "                        visited[nei] = True\n",
    "                for i in range(1,5):\n",
    "                    # print(x, bin(c))\n",
    "                    if c >> i & 1 == 0:\n",
    "                        color[x] = i\n",
    "                        break\n",
    "                # print(x, q, color)\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            if not visited[i]:\n",
    "                bfs(i)\n",
    "        return color[1:]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 哈希表（数组）实现\n",
    "    # https://leetcode.cn/problems/flower-planting-with-no-adjacent/solutions/2227318/liang-chong-xie-fa-ha-xi-biao-shu-zu-wei-7hm8/\n",
    "    def gardenNoAdj1(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in paths:\n",
    "            g[u - 1].append(v - 1)\n",
    "            g[v - 1].append(u - 1)  # 建图\n",
    "\n",
    "        color = [0] * n\n",
    "        for i, nodes in enumerate(g):\n",
    "            color[i] = (set(range(1, 5)) - {color[j] for j in nodes}).pop()\n",
    "\n",
    "        return color\n",
    "\n",
    "\n",
    "\n",
    "    # 位运算\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in paths:\n",
    "            g[u - 1].append(v - 1)\n",
    "            g[v - 1].append(u - 1)  # 建图\n",
    "            \n",
    "        color = [0] * n\n",
    "        for i, nodes in enumerate(g):\n",
    "            mask = 1  # 由于颜色是 1~4，把 0 加入 mask 保证下面不会算出 0\n",
    "            for j in g[i]:\n",
    "                mask |= 1 << color[j]\n",
    "\n",
    "            mask = ~mask\n",
    "            # Python 没有统计尾零的库函数，可以枚举，或者求 lowbit 的二进制长度减一\n",
    "            color[i] = (mask & -mask).bit_length() - 1\n",
    "\n",
    "        return color\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "            \n",
    "        ans = [7] * n\n",
    "        for i in range(n):\n",
    "            mask = 0\n",
    "            for x in g[i]:\n",
    "                mask |= 1 << (ans[x] - 1)\n",
    "            mask = (~mask) & 15\n",
    "            ans[i] = ((mask & -mask) - 1).bit_count() + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        Map = {}\n",
    "        # 这个建立的是单向图，要构建双向图\n",
    "        for st , end in paths:\n",
    "            if st in Map:\n",
    "                Map[st].append(end)\n",
    "            else:\n",
    "                Map[st] = [end]\n",
    "            if end in Map:\n",
    "                Map[end].append(st)\n",
    "            else:\n",
    "                Map[end] = [st]\n",
    "        \n",
    "        res = [1]*n \n",
    "        visted = [False]*(n+1)\n",
    "\n",
    "        for i in Map.keys():\n",
    "            if visted[i]:\n",
    "                continue \n",
    "            visted[i] = True \n",
    "            # 遍历其相邻的节点,统计其颜色\n",
    "            used = []\n",
    "            for neb in Map[i]:\n",
    "                used.append(res[neb-1])\n",
    "            for color in range(1,5):\n",
    "                if color not in used:\n",
    "                    res[i-1] = color\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        relation = defaultdict(list)\n",
    "        for g1, g2 in paths:\n",
    "            relation[g1].append(g2)\n",
    "            relation[g2].append(g1)\n",
    "        \n",
    "        result = [0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            colors = set(range(1, 5)) - set(result[g-1] for g in relation[i])\n",
    "            result[i-1] = colors.pop()\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def gardenNoAdj(self, N, paths):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type paths: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        #每个花园最多和3个别的花园相连\n",
    "        # if not paths:\n",
    "        #     return []\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(list)\n",
    "        \n",
    "        for path in paths:\n",
    "            x0, y0 =  path[0], path[1]\n",
    "            dic[x0].append(y0)\n",
    "            dic[y0].append(x0)\n",
    "            \n",
    "        # print dic\n",
    "        res = [-1 for _ in range(N + 1)]\n",
    "        # print len(dic.keys())\n",
    "        for i in dic.keys():\n",
    "            neibors = dic[i]\n",
    "            used = [0 for _ in range(5)]\n",
    "            for neibor in neibors:\n",
    "                if res[neibor] != -1:\n",
    "                    used[res[neibor]] = 1\n",
    "            if sum(used) == 0:\n",
    "                res[i] = 1\n",
    "            else:\n",
    "                for j in range(1, 5):\n",
    "                    if used[j] == 0:\n",
    "                        res[i] = j\n",
    "                        break\n",
    "        # print res\n",
    "        for i, x in enumerate(res):\n",
    "            if x == -1:\n",
    "                res[i] = 1\n",
    "        return res[1:]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        ans = [0] * n\n",
    "        for x in range(n):\n",
    "            used = {ans[y] for y in g[x]}\n",
    "            for c in range(1, 5):\n",
    "                if c not in used:\n",
    "                    ans[x] = c\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in paths:\n",
    "            dct[i-1].append(j-1)\n",
    "            dct[j-1].append(i-1)\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            if ans[i]:\n",
    "                continue\n",
    "            lst = [ans[x] for x in dct[i]]\n",
    "            for c in range(1, 5):\n",
    "                if c not in lst:\n",
    "                    ans[i] = c\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        graph = {}\n",
    "        for edge in paths:\n",
    "            if edge[0] not in graph:\n",
    "                graph[edge[0]] = [edge[1]]\n",
    "            elif edge[0] in graph:\n",
    "                graph[edge[0]].append(edge[1])\n",
    "            if edge[1] not in graph:\n",
    "                graph[edge[1]] = [edge[0]]\n",
    "            elif edge[1] in graph:\n",
    "                graph[edge[1]].append(edge[0])\n",
    "        ans = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            choices = [1, 2, 3, 4]\n",
    "            if i in graph:\n",
    "                for garden in graph[i]:\n",
    "                    if ans[garden] in choices:\n",
    "                        choices.remove(ans[garden])\n",
    "                ans[i] = choices[0]\n",
    "            elif i not in graph:\n",
    "                ans[i] = 1\n",
    "        return ans[1:]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for x,y in paths:\n",
    "            graph[x-1].append(y-1)\n",
    "            graph[y-1].append(x-1)\n",
    "\n",
    "        res = [0]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            used = {res[y] for y in graph[i]}\n",
    "            for c in range(1,5):\n",
    "                if c not in used:\n",
    "                    res[i] = c\n",
    "                    break\n",
    "\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        # paths\n",
    "        garden = [[] for i in range(n)]\n",
    "        # print(garden)\n",
    "        for x,y in paths:\n",
    "            garden[x - 1].append(y - 1)\n",
    "            garden[y - 1].append(x - 1)\n",
    "        # print(garden)\n",
    "\n",
    "        ans = []\n",
    "        color = [0] * n\n",
    "        for i, nodes in enumerate(garden):\n",
    "            color[i] = (set(range(1,5)) - {color[j] for j in nodes}).pop()\n",
    "        # print(color)\n",
    "        return color\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        ss = defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            x, y = x - 1, y - 1\n",
    "            ss[x].append(y)\n",
    "            ss[y].append(x)\n",
    "        res = [0] * n\n",
    "        colors = tuple(range(1, 5))\n",
    "        for x in range(n):\n",
    "            used = [res[y] for y in ss[x]]\n",
    "            for i in colors:\n",
    "                if i not in used:\n",
    "                    res[x] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        e = {}\n",
    "        for i in range(len(paths)):\n",
    "            u,v = paths[i]\n",
    "            if u not in e.keys():\n",
    "                e[u] = [v]\n",
    "            else:\n",
    "                e[u].append(v)\n",
    "            if v not in e.keys():\n",
    "                e[v] = [u]\n",
    "            else:\n",
    "                e[v].append(u)\n",
    "        res = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            color = [0,0,0,0,0]\n",
    "            color[res[i]]=1\n",
    "            if i in e.keys():\n",
    "                for v in e[i]:\n",
    "                    if res[v] != 0:\n",
    "                        color[res[v]] = 1\n",
    "\n",
    "            for j in range(1,5):\n",
    "                if color[j]==0:\n",
    "                    res[i]=j\n",
    "                    break\n",
    "        return res[1:]\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = [0] * n\n",
    "        for x in range(n):\n",
    "            used = {ans[y] for y in g[x]}\n",
    "            for c in range(1, 5):\n",
    "                if c not in used:\n",
    "                    ans[x] = c\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        relation_dict = defaultdict(list)\n",
    "        for g1, g2 in paths:\n",
    "            relation_dict[g1].append(g2)\n",
    "            relation_dict[g2].append(g1)\n",
    "\n",
    "        result = [0]*n\n",
    "        for i in range(1, n+1):\n",
    "            color = set(range(1, 5)) - set(result[g-1] for g in relation_dict[i])\n",
    "            result[i-1] = color.pop()\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = [0] * n\n",
    "        for x in range(n):\n",
    "            used = {ans[y] for y in g[x]}\n",
    "            for c in range(1, 5):\n",
    "                if c not in used:\n",
    "                    ans[x] = c\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        grid = defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            x, y = x-1, y-1\n",
    "            grid[x].append(y)\n",
    "            grid[y].append(x)\n",
    "\n",
    "        result = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            # 对于每个花园 i，我们先找出与 i 相邻的花园 j，并将 j 花园中种植的花的种类标记为已使用\n",
    "            used = {result[j] for j in grid[i]}\n",
    "            # 然后我们从花的种类 1 开始枚举，直到找到一个未被使用的花的种类 c，将 c 标记为 i 花园中种植的花的种类，然后继续枚举下一个花园\n",
    "            for c in range(1, n+1):\n",
    "                if c not in used:\n",
    "                    result[i] = c\n",
    "                    break\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        parks = dict()\n",
    "        for x, y in paths:\n",
    "            if x in parks:\n",
    "                parks[x].append(y)\n",
    "            else:\n",
    "                parks[x] = [y]\n",
    "            if y in parks:\n",
    "                parks[y].append(x)\n",
    "            else:\n",
    "                parks[y] = [x]\n",
    "\n",
    "        ans = [0] * n\n",
    "        ans[0] = 1\n",
    "\n",
    "        def setflower(x):\n",
    "            kinds = [1, 2, 3, 4]\n",
    "            if x in parks:\n",
    "                for nb in parks[x]:    # 遍历park x的相邻花园\n",
    "                    kind = ans[nb - 1]\n",
    "                    if kind != 0 and kind in kinds: # 相邻的park已经有花种类\n",
    "                        kinds.remove(kind)\n",
    "                #设置第一种不是相邻的即可\n",
    "                if len(kinds) > 0:\n",
    "                    ans[x - 1] = kinds[0]\n",
    "            else:\n",
    "                ans[x - 1] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            setflower(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, j in paths:\n",
    "            g[i - 1].append(j - 1)\n",
    "            g[j - 1].append(i - 1)\n",
    "        \n",
    "        vis = [True] + [False] * (n - 1)\n",
    "        ans = [0] * n\n",
    "        for z in range(n):\n",
    "            if ans[z] == 0:\n",
    "                queue = deque([z])\n",
    "                while queue:\n",
    "                    node = queue.popleft()\n",
    "                    have = [False] * 5\n",
    "                    for nei in g[node]:\n",
    "                        have[ans[nei]] = True\n",
    "                        if not vis[nei]:\n",
    "                            vis[nei] = True\n",
    "                            queue.append(nei)\n",
    "                    for i in range(1, len(have)):\n",
    "                        if not have[i]:\n",
    "                            ans[node] = i\n",
    "                            break\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            d[i] = 0\n",
    "        graph = [[] for i in range(n)]\n",
    "        for v1,v2 in paths:\n",
    "            graph[v1-1].append(v2-1)\n",
    "            graph[v2-1].append(v1-1)\n",
    "        for i in range(n):\n",
    "            tmp = [0,0,0,0]\n",
    "            for p in graph[i]:\n",
    "                if d[p] > 0:\n",
    "                    tmp[d[p]-1] = 1\n",
    "            for j in range(4):\n",
    "                if tmp[j] == 0:\n",
    "                    d[i] = j+1\n",
    "                    break\n",
    "        res = [0 for i in range(n)]\n",
    "        for k in d:\n",
    "            res[k] = d[k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in paths:\n",
    "            x, y = x - 1, y - 1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = [0] * n\n",
    "        for x in range(n):\n",
    "            used = {ans[y] for y in g[x]}\n",
    "            for c in range(1, 5):\n",
    "                if c not in used:\n",
    "                    ans[x] = c\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        adj = defaultdict(list)\n",
    "        for p in paths:\n",
    "            adj[p[0]].append(p[1])\n",
    "            adj[p[1]].append(p[0])\n",
    "        \n",
    "        colors = [-1]*n\n",
    "        for i in range(n):\n",
    "            adj_colors = []\n",
    "            if len(adj[i+1])>0:\n",
    "                for adj_node in adj[i+1]:\n",
    "                    adj_colors.append(colors[adj_node-1])\n",
    "            for c in range(1,5):\n",
    "                if not c in adj_colors:\n",
    "                    colors[i] = c\n",
    "        return colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        # paths\n",
    "        garden = [[] for i in range(n)]\n",
    "        print(garden)\n",
    "        for x,y in paths:\n",
    "            garden[x - 1].append(y - 1)\n",
    "            garden[y - 1].append(x - 1)\n",
    "        print(garden)\n",
    "\n",
    "        ans = []\n",
    "        color = [0] * n\n",
    "        for i, nodes in enumerate(garden):\n",
    "            color[i] = (set(range(1,5)) - {color[j] for j in nodes}).pop()\n",
    "        print(color)\n",
    "        return color\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        dic=defaultdict(set)#储存相邻花园\n",
    "        ans=[1]*(n+1)\n",
    "        for path in  paths:\n",
    "            dic[path[0]].add(path[1])\n",
    "            dic[path[1]].add(path[0])\n",
    "            neibor_color = set([ans[j] for j in dic[path[1]]])\n",
    "            alti_color=[ color for color in range(1,5) if  color not in neibor_color]\n",
    "            ans[path[1]]=min(alti_color)\n",
    "        return ans[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        m = [[] for _ in range(n)]\n",
    "        for i,j in paths:\n",
    "            m[i-1].append(j-1)\n",
    "            m[j-1].append(i-1) \n",
    "        colour = [0]*n\n",
    "        print(m)\n",
    "        for i,node in enumerate(m):\n",
    "            #print(colour)\n",
    "            #print({colour[j] for j in node})\n",
    "            #print(set(range(1,5))-{colour[j] for j in node})\n",
    "            colour[i] = (set(range(1,5))-{colour[j] for j in node}).pop()\n",
    "        return colour"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(set)\n",
    "        for (x, y) in paths:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        \n",
    "        res = [0]*(n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            tmp = {1,2,3,4}\n",
    "            for x in g[i]:\n",
    "                tmp.discard(res[x])\n",
    "            res[i] = tmp.pop()\n",
    "            \n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        dic=defaultdict(set)#储存相邻花园\n",
    "        ans=[1]*(n+1)\n",
    "        for path in  paths:\n",
    "            dic[path[0]].add(path[1])\n",
    "            dic[path[1]].add(path[0])\n",
    "            ans[path[1]]=min([ color for color in range(1,5) if  color not in set([ans[j] for j in dic[path[1]]])])\n",
    "        return ans[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        not_pass = set([i for i in range(1, n + 1)])\n",
    "        res = [0] * n\n",
    "        current = {1}\n",
    "        routes = {}\n",
    "        for p in paths:\n",
    "            routes.setdefault(p[0], set()).add(p[1])\n",
    "            routes.setdefault(p[1], set()).add(p[0])\n",
    "        while current or not_pass:\n",
    "            if not current:\n",
    "                p = not_pass.pop()\n",
    "                current.add(p)\n",
    "                not_pass.add(p)\n",
    "                continue\n",
    "            next_current = set()\n",
    "            for p in current:\n",
    "                if p not in not_pass:\n",
    "                    continue\n",
    "                not_pass.remove(p)\n",
    "                if p not in routes:  # 无连通 设置成1\n",
    "                    res[p - 1] = 1\n",
    "                    continue\n",
    "                f_types = {1, 2, 3, 4}\n",
    "                for r_p in routes[p]:\n",
    "                    if res[r_p - 1] in f_types:\n",
    "                        f_types.remove(res[r_p - 1])\n",
    "                    else:\n",
    "                        next_current.add(r_p)\n",
    "                res[p - 1] = f_types.pop()\n",
    "            current = next_current\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * n\n",
    "        num_class = 4\n",
    "        g = defaultdict(set)\n",
    "        allowed = [set(range(1, num_class + 1)) for _ in range(n)]\n",
    "        for a, b in paths:\n",
    "            a, b = a - 1, b - 1\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "\n",
    "        for i in range(n):\n",
    "            if ans[i] != -1:\n",
    "                continue\n",
    "            ans[i] = allowed[i].pop()\n",
    "            for pp in g[i]:\n",
    "                if ans[pp] == -1:\n",
    "                    allowed[pp].discard(ans[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, number, category, ans, graden):\n",
    "        if number in category: return\n",
    "        used = set()\n",
    "        for neighbours in graden[number]:  # 查看花园number的邻居都使用过那些花\n",
    "            if neighbours in category:\n",
    "                used.add(category[neighbours])\n",
    "\n",
    "        # 执行完之后就能直到哪些花是可以使用的\n",
    "        for i in range(1, 5):\n",
    "            if i not in used:\n",
    "                flower = i\n",
    "                break\n",
    "        ans[number-1] = i\n",
    "        category[number] = i\n",
    "        for neighbours in graden[number]:\n",
    "            self.dfs(neighbours, category, ans, graden)\n",
    "\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        graden = [[] for _ in range(n+1)]  # 每个花园的邻接花园\n",
    "        number = 1  # 遍历到那个花园了\n",
    "        category = {}  # 各个花园使用的花的种类\n",
    "        ans = [0] * n\n",
    "        for x, y in paths:\n",
    "            graden[x].append(y)\n",
    "            graden[y].append(x)\n",
    "        i=1\n",
    "        while i<=n:\n",
    "            if i not in category:\n",
    "                self.dfs(i,category,ans,graden)\n",
    "            i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        G = [[] for _ in range(n)]\n",
    "        for i, j in paths:\n",
    "            G[i-1].append(j-1)\n",
    "            G[j-1].append(i-1)\n",
    "        ans = [-1]*n\n",
    "        def dfs(i):\n",
    "            if ans[i] == -1:\n",
    "                ans[i] = list(set(range(1, 5)) - set([ans[nei] for nei in G[i]]))[0]\n",
    "                for nei in G[i]:\n",
    "                    dfs(nei)\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:\n",
    "        # 创建图的邻接表表示\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in paths:\n",
    "            graph[x - 1].append(y - 1)\n",
    "            graph[y - 1].append(x - 1)\n",
    "        \n",
    "        # 创建花园花的种类列表，初始为0\n",
    "        flowers = [0] * n\n",
    "        \n",
    "        def dfs(node):\n",
    "            # 如果当前花园已经选择了花，则直接返回\n",
    "            if flowers[node] != 0:\n",
    "                return\n",
    "            \n",
    "            # 遍历四种花的种类\n",
    "            for i in range(1, 5):\n",
    "                is_valid = True\n",
    "                # 检查相邻花园是否有相同的花\n",
    "                for neighbor in graph[node]:\n",
    "                    if flowers[neighbor] == i:\n",
    "                        is_valid = False\n",
    "                        break\n",
    "                if is_valid:\n",
    "                    flowers[node] = i\n",
    "                    # 递归搜索下一个花园\n",
    "                    for neighbor in graph[node]:\n",
    "                        dfs(neighbor)\n",
    "                    break\n",
    "        \n",
    "        # 从每个花园开始进行深度优先搜索\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        return flowers"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
